package com.zmh.arithmetic.backtracking;

import java.util.ArrayList;
import java.util.List;

/**
 * n皇后 no.51
 *
 * @author zmh
 * @create 2019-07-31 16:13
 **/
public class NQueensV2 {
    private List<List<String>> resultList = new ArrayList<>();
    private int[] queens;
    //    private int[] rows;
    private int[] columns;
    private int[] leftUps;
    private int[] rightUps;
    private int n;

    public List<List<String>> solveNQueens(int n) {
        queens = new int[n];
        columns = new int[n];
        leftUps = new int[2 * n];
        rightUps = new int[2 * n];
        this.n = n;
        calcResult(0);
        return resultList;
    }

    private void calcResult(int row) {
        if (row == n) {
            return;
        }

        for (int i = 0; i < n; i++) {
            if (isOk(row, i)) {
                add(row, i);
                calcResult(row + 1);
                if (row == n - 1) {
                    resultList.add(itemToList(queens));
                }
                remove(row, i);
            }
        }
    }

    private void add(int row, int column) {
        queens[row] = column;
        columns[column] = 1;
        leftUps[row - column + n] = 1;
        rightUps[row + column] = 1;
    }

    private void remove(int row, int column) {
        queens[row] = 0;
        columns[column] = 0;
        leftUps[row - column + n] = 0;
        rightUps[row + column] = 0;
    }

    private boolean isOk(int row, int colum) {
        int result = columns[colum] + leftUps[row - colum + n] + rightUps[row + colum];
        return result > 0 ? false : true;
    }

    private List<String> itemToList(int[] item) {
//        System.out.println("item size " + item.size());
        List<String> list = new ArrayList<>();
        for (int i : item) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < item.length; j++) {
                if (i == j) {
                    sb.append("Q");
                } else {
                    sb.append(".");
                }
            }
            list.add(sb.toString());
        }
        return list;
    }

    public static void main(String[] args) {
        NQueensV2 nQueens = new NQueensV2();
        List<List<String>> lists = nQueens.solveNQueens(4);
        System.out.println(lists.toString());
    }
}
